package com.剑指offer.第四章;

public class 排序的循环链表 {

    /**
     */
    public static void resolve(ListNode head, int num) {
        ListNode node = new ListNode(num);
        // 考虑两种边界情况
        if (head == null) { // 当一个节点多没有时
            head = node;
            head.next = head;
        } else if (head.next == head) { // 当有一个节点时
            head.next = node;
            node.next = head;
        } else {
            ListNode cur = head;
            ListNode next = head.next;
            // 保存每次循环之后的节点最大的节点。
            ListNode biggest = head;

            /**
             * 一直循环，直到找出存在的两个节点就退出循环或者循环完毕
             */
            while (!(cur.val <= node.val && next.val >= node.val) && next != head) {
                cur = cur.next;
                next = next.next;
                if (cur.val >= biggest.val) {
                    biggest = cur;
                }
            }

            if (cur.val <= node.val && next.val >= node.val) {//  正常情况 最大值或者两个节点都存在
                node.next = next;
                cur.next = node;
            } else { // 这种情况是 传入一个最小值时
                node.next = biggest.next;
                biggest.next = node;
            }

        }
    }

    public static void main(String[] args) {

    }

}
